class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(auto e : nums)
        {
            sum += e;
        }
        if(sum % 2)
        {
            return false;
        }

        int target = sum / 2;

        int n = nums.size();
        vector<vector<bool>> dp(n+1, vector<bool>(target+1, false));

        dp[0][0] = true;
        // for(int j = 1; j <= target; ++j)
        // {
            // dp[0][j] = false;
        // }

        for(int i = 1; i <= n; ++i)
        {
            int num = nums[i-1];
            for(int j = 0; j <= target; ++j)
            {
                if(num > j)
                {
                    dp[i][j] = dp[i-1][j];
                }
                else
                {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-num];
                }
            }
        }

        return dp[n][target];
    }
};
